package listbyorder.access101_200.test188;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/6/15 11:01
 */
public class Solution2 {

    public int maxProfit(int k, int[] prices) {
        if (prices.length == 0) {
            return 0;
        }
        int K = Math.min(k, prices.length / 2);
        int[] dp = new int[K + 1];
        int min[] = new int[K + 1];
        for (int i = 1; i <= K; i++) {
            min[i] = prices[0];
        }
        for (int i = 1; i < prices.length; i++) {
            for (int kk = 1; kk <= K; kk++) {
                min[kk] = Math.min(prices[i] - dp[kk - 1], min[kk]);
                dp[kk] = Math.max(dp[kk], prices[i] - min[kk]);
            }
        }
        return dp[K];
    }

}
